package com.chenxys.algorithm.newbie;

import com.chenxys.algorithm.common.ListNode;

/**
 * <p>
 *      两个有序链表合并<br/>
 *      <a href="https://leetcode.com/problems/merge-two-sorted-lists">测试链接</a><br/>
 *      例: 1 -> 3 -> 3 -> 5 -> 7   2 -> 2 -> 3 -> 3 -> -> 7
 *      返回 1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 3 -> 5 -> 7 -> 7
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/30/23 3:13 PM
 * @Copyright ©
 */
public class MergeTwoSortedLinkedList {
    /**
     * <p>
     *     合并两个有序链表,并返回合并后的有序链表
     * </p>
     * @param head1 有序链表1
     * @param head2 有序链表2
     * @return 合并后的有序链表
     */
    public static ListNode mergeTwoLists (ListNode head1, ListNode head2){
        if (head1 == null || head2 == null) return head1 == null ? head2 : head1;
        // [确定返回链表的头节点]返回后的链表第一个节点,如果链表1的值<=链表2,将链表1第一个节点给返回后链表,否则给链表2
        ListNode head = head1.val <= head2.val ? head1 : head2;
        // 小头的下一个
        ListNode cur1 = head.next;
        // 大头的第一个
        ListNode cur2 = head == head1 ? head2 : head1;
        ListNode pre = head;
        while (cur1 != null && cur2 != null){
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        // 如果有一个链表当前节点为空,但另一个链表当前节点不为空,则将不为空的哪一个加入到返回后链表
        pre.next = cur1 != null ? cur1 : cur2;
        return head;
    }
}
